1. Field of the Invention
This invention relates to a sorting method and apparatus for sorting numerical data inputted in a time series and identifiers corresponding to the numerical data in the order of the size of the numerical data.
2. Description of the Prior Art
In a character recognition apparatus according to the prior art, an input image pattern obtained by an image pick-up device generally is subjected to a distance computation (comparison) with respect to standard patterns of respective characters stored beforehand in an internal memory, the one standard pattern which most closely approximates the input image pattern (namely the standard pattern having the shortest distance) is extracted based on the results of the computation, and a character code corresponding to the extracted standard pattern is outputted as the results of character recognition of the input image pattern.
FIG. 6 illustrates an example of the simplified arrangement of such a conventional character recognition apparatus.
As shown in FIG. 6, an image pattern (input image pattern) enters from a scanner (an image pick-up device or image reader) 1 via a scanner interface 2 and is written in an image memory 3 by a central processing unit (CPU) 4.
Next, the input image pattern stored in the image memory 3 is read out under the control of the CPU 4 and sent to an arithmetic circuit 5-2 of an identification circuit 5.
A dictionary memory 5-1 stores various character codes and standard image patterns corresponding to these character codes. The arithmetic circuit 5-2 performs a distance computation to compute the distance between the input image pattern from the image memory 3 and the standard image patterns in the dictionary memory 5-1.
This distance computation is performed by comparing each of the plurality of standard image patterns with the single input image pattern, thereby obtaining computation results (distance data) regarding each standard image pattern.
A memory 5-4 for storing the results of identification constitutes a sorting circuit. The memory 5-4 stores the identifier of the relevant standard pattern, namely the character code, at an address corresponding to the results of distance computation (distance data) received from the arithmetic circuit 5-2 via a write circuit 5-3. The write circuit 5-3 also constitutes the sorting circuit.
The character codes stored in the memory 5-4 are read out by the CPU 4 in the order of the addresses, namely in order from the smaller to the larger distances. These character codes are displayed on a CRT display unit 7 via a CRT interface (I/F) 6. The smaller the distance, the closer the standard image pattern of the corresponding code approximates the input image pattern.
The factual operation of this sorting circuit will now be described in simple terms.
When an image pattern of one character initially enters from the scanner 1, this input image pattern is sent to the arithmetic circuit 5-2 via the image memory 3. The arithmetic circuit 5-2 computes the distance between this input image pattern and the standard image pattern of the first character, e.g., "A", stored in the dictionary memory 5-1, and the write circuit 5-3 stores the character code of the character "A" at an address in the memory 5-4 corresponding to the distance data, which is the result of distance computation.
Next, the arithmetic circuit 5-2 reads the standard image pattern of the next character "B" out of the dictionary memory 5-1 and performs a distance computation with regard to the input image pattern, just as in the case of the character "A". The write circuit 5-3 stores the character code of the character "B" at an address in the memory 5-4 corresponding to the distance data regarding the standard image pattern of character "B".
By thenceforth repeating this procedure in successive fashion, character codes of the standard image patterns are successively stored at addresses of the memory 5-4 corresponding to the distances between the standard image patterns and the input image pattern. Thus, computations of the distance between the input image pattern and the standard image patterns corresponding to all of the character codes stored in the dictionary memory 5-1 end. When the results are stored at the addresses of the memory 5-4 that correspond to the respective items of distance data, the CPU 4 reads the character codes out of the memory 5-4 sequentially in order starting from the smallest address of the memory, i.e., starting from the character code of the character best approximating the input image pattern. These character codes or the stored character patterns themselves are displayed on the CRT display unit 7. In this way the operator is informed of the candidates for character recognition in accordance with the size of the computed distances. This is done by displaying the candidates in the order in which they best approximate the input image pattern, by way of example
In this type of conventional sorting circuit used in a character recognition apparatus, the arrangement is such that the character code of the standard image pattern having the shortest distance with respect to one input image pattern is stored in memory with the distance data thereof serving as the address, as mentioned above. Therefore, in a case where distance data regarding a character "A" and a character "F" in the foregoing example indicates the same value, the content (the character "A" code data) stored at the address corresponding to the distance data relative to the standard image pattern of character code "A" computed at a preceding point in time will be rewritten as the character "F" code data which has the same distance data (address) computed at a later point in time. Consequently, the operator cannot be informed of the fact that two or more standard image patterns of character codes ("A" and "F" in this case) have the same distance data, i.e., all of them approximate the input image pattern in the same extent. Thus, the operator is informed of the fact that only "F", which is the result of the latter computation, is the character best approximating the input image pattern even though both "A" and "F" approximate it best. As a result, the conventional sorting circuit of a character recognition apparatus is defective in that the operator may not recognize a character correctly.
In order to solve this problem, consideration has been given to providing addresses of the identification storage memory 5-4 that correspond to all distance data regarding a single input image pattern with a plurality of storage areas (the maximum number of which would be the number of character codes stored in the dictionary memory 5-1) respectively. However, in a case where there are several hundred to several thousand character codes, the capacity of the memory 5-4 would have to be enormous (i.e., a memory capacity equivalent to the number of addresses multiplied by the number of character codes). This would give rise to new drawbacks, namely a higher cost for the apparatus and a longer memory access time.